[BZOJ4331] [JSOI2012]越狱老虎桥

[BZOJ4331] [JSOI2012]越狱老虎桥

题意: 在任意加入一条边的情况下,求 割一条边使图不从1联通的最小割边的 最大值

首先根据题目的意思,可以下对这个无向图中 进行边双联通分量 缩点

建出一棵边双生成树,树边即为原图的割边,树边带权

割掉双联通分量内部的边显然没有意义,所以忽略掉他们,下文所提的均是树上节点和边

在不额外加边的情况下,而割掉树边会使子树内部的点断开

在加入边的情况下,若加入一条 \(1-u\) 的边,则形成了一个 \(1-u\) 的环,环是无法通过割开一条边断开的

而连接树上两个节点 \((u,v)\) 的情况,把图展开后,就会发现,就是把 \(u,v\) 路径上所有的点都缩进了同一个环

此时断掉环上的边显然不合法,而不在环上的边,只需要随便断掉一条,就能让一个点不连通

也就是说,答案是 (去掉某个点对 \((u,v)\) 路径上的所有边,剩下的边中最小值) 的最大值

设答案为 \(ans\)

这个问题实际上等价于所有的 \(e\in E,w(e)\leq ans\) 的边无法被一条路径完全覆盖

做法1:

考虑二分答案,把每条 \(e\in E,w(e)\leq ans\) 的边的权值设为1,求出直径长度判断是否可以用一条路径完全覆盖即可

复杂度为 \(O(n\log n)\)

做法2:

实际上这个问题就是 (选择了合法的3条边中边权的最大值) 的最小值

对于当前节点 \(u\) ,实际合法情况有

1.选择了一条祖先的边,和2条儿子岔开的边

2.选择了3条垂下的岔开的边,这个合并时比较诡异可以看代码

\(\text{dp}\) 维护即可,复杂度为 \(O(n)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
typedef long long ll;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,const T &b){ ((a>b)&&(a=b)); }

char IO;
template <class T=int> T rd(){
T s=0; int f=0;
while(!isdigit(IO=getchar())) if(IO=='-') f=1;
do s=(s<<1)+(s<<3)+(IO^'0');
while(isdigit(IO=getchar()));
return f?-s:s;
}

const int N=5e5+10,INF=1e9+10;

int n,m;
struct Edge{
int to,nxt,w;
} e[N*6];
int head[N],ecnt;
void AddEdge(int u,int v,int w) {
e[++ecnt]=(Edge){v,head[u],w};
head[u]=ecnt;
}
#define erep(u,i) for(int i=head[u],v=e[i].to;i;i=e[i].nxt,v=e[i].to)

int low[N],t[N],id[N],scc,dfn;
int stk[N],top;
void dfs(int u,int f) {
low[u]=t[u]=++dfn;
stk[++top]=u;
erep(u,i) if(v!=f) {
if(!t[v]) dfs(v,u),cmin(low[u],low[v]);
else cmin(low[u],t[v]);
}
if(low[u]==t[u]){
int v; ++scc;
do v=stk[top--],id[v]=scc;
while(v!=u);
}
}

int head2[N];
void AddEdge2(int u,int v,int w) {
e[++ecnt]=(Edge){v,head2[u],w};
head2[u]=ecnt;
}
#define erep2(u,i) for(int i=head2[u],v=e[i].to,w=e[i].w;i;i=e[i].nxt,v=e[i].to,w=e[i].w)

int ans=INF;
int dp[N][4],tmp[4],g[N];

void dfs1(int u,int f) {
dp[u][0]=0,dp[u][1]=dp[u][2]=dp[u][3]=INF;
erep2(u,i) if(v!=f) {
g[v]=min(g[u],w),dfs1(v,u);
memset(tmp,63,sizeof tmp);
rep(j,0,3) {
cmin(tmp[j],dp[u][j]);
if(j<3) cmin(tmp[j+1],max(dp[u][j],w));
rep(k,0,3-j) cmin(tmp[j+k],max(dp[u][j],dp[v][k]));
}
rep(j,0,3) dp[u][j]=tmp[j];
}
cmin(ans,dp[u][3]);
cmin(ans,max(g[u],dp[u][2]));
}


int main(){
n=rd(),m=rd();
rep(i,1,m) {
int u=rd(),v=rd(),w=rd();
AddEdge(u,v,w),AddEdge(v,u,w);
}
dfs(1,0);
rep(u,1,n) erep(u,i) if(id[u]!=id[v]) AddEdge2(id[u],id[v],e[i].w);
g[id[1]]=INF,dfs1(id[1],0);
printf("%d\n",ans==INF?-1:ans);
}